package ch03;

public class BinarySearchST<Key extends Comparable<Key>,Value> {

    private Key[] keys;
    private Value[] vals;
    private int N;


    public BinarySearchST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[])new Object[capacity];
    }

    public int size(){
        return N;
    }

    public Value get(Key key){
        int i = rank(key);
        if (i < N||keys[i].compareTo(key)==0) {
            return vals[i];
        }
        return null;


    }


    public int rank(Key key){
        int lo = 0;
        int hi = N - 1;
        while (lo <= hi) {
            int mid = lo + (hi-lo)/2;
            int cmp = key.compareTo(keys[mid]);
            if(cmp<0)
                hi = mid - 1;
            else if(cmp>0)
                lo = mid + 1;
            else
                return mid;
        }
        return lo;
    }

    public void put(Key key, Value value) {
        int i = rank(key);
        if (i < N||keys[i].compareTo(key)==0) {
            vals[i] = value;
            return;
        }
        for (int j = N; j > i; j--) {
            keys[j] = keys[j - 1];
            vals[j] = vals[j - 1];
        }
        keys[i] = key;
        vals[i] = value;
        N++;
    }

    public void delete(Key key){
        if (N <= 0) {
            return;
        }
        int i = rank(key);

        if (i < N && key.compareTo(keys[i]) == 0) {

            for (int j= i;j<N-1;j++) {
                keys[j] = keys[j + 1];
                vals[j] = vals[j + 1];

            }

        }

    }

    public Key min(){
        return keys[0];
    }
    public Key max(){
        return keys[N-1];
    }

    public Key select(int k) {
        return keys[k];
    }

    void rightBinary(int[] nums,int target){
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            }else{
                l = mid;
            }
        }
    }
    void binary(int[] nums,int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (nums[mid] == target) {
                break;
            } else if (nums[mid] < target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }

        }
    }
}
